POI2013 Taxis

POI2013 Taxis

题目大意:

你当前在0处，d处有一个车站，你的家在m处。你现在想坐出租车回家，但出租车只会从车站出发，并且第i辆车只被允许开$x_i$的距离(是路程，而不是位移)。问你回家最少要几辆出租车。

$PS.$ 比较简单的贪心题。

题解：

有一个贪心思路比较显然：你在到达车站前，派出的车的$x_i$越大，我们所走的重复的路段越小。因而为了尽快到达d，我们可以直接按照$x_i$从大到小依次打车。

但这样却并不能保证我们能到家。因为我们可能为了用尽量少的车到d而把大的车都用完了，以至于没有一辆车能将你从d送到m去了。

那怎么办呢？我们发现，若你在d，只需要一辆$x_i>=m-d$的车即可回家。因而一开始，我们给车排序后，先预留一辆大于等于m-d的最小的车。用其他的车先使自己到达d即可。

(有可能用其他的车可以直接到家，这样就不用加上预留的车的代价了)

Code：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
void Rd(ll&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=500005;
int n;
ll m,d,num[N];
int solve(){
	sort(num+1,num+1+n);
	int id=lower_bound(num+1,num+1+n,m-d)-num;
	ll p=0;int cnt=0;
	for(int i=n;i>=1;i--){
		if(i==id)continue;
		if(p<d){
			if(num[i]>d-p){
				p+=num[i]-d+p;
				cnt++;
			}else break;	
		}else break;
	}
	if(p<d){
		if(num[id]<m-p+d-p)return 0;
		else return cnt+1;
	}else{
		if(p<m)return cnt+1;
		return cnt;
	}
}
int main(){
	cin>>m>>d>>n;
	for(int i=1;i<=n;i++)Rd(num[i]);
	printf("%d\n",solve());
	return 0;
}